/*
 * @lc app=leetcode.cn id=123 lang=golang
 *
 * [123] 买卖股票的最佳时机 III
 */

// 1. 动态规划
// dp[i][j] i代表第几天，j代表这一天结束的时候是否持有股票
// @lc code=start
func maxProfit(prices []int) int {
	if len(prices) == 1 {
		return 0
	}
	dp := make([][]int, len(prices))
	for i := 0; i < len(prices); i++ {
		dp[i] = make([]int, 5)
	}
	dp[0][0] = 0          // 未持有股票，没有买,
	dp[0][1] = -prices[0] // 持有股票，  第一次买
	dp[0][2] = 0          // 未持有股票，第一次卖
	dp[0][3] = -prices[0] // 持有股票，  第二次买
	dp[0][4] = 0          // 未持有股票，第二次卖
	for i := 1; i < len(prices); i++ {
		dp[i][0] = dp[i-1][0]                            // 今天结束没买，前一天也没买
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]) // 今天结束第一次买，要么前一天买的，要么今天买的
		dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i]) // 今天结束第一次卖，要么前一天卖的，要么今天卖的
		dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i]) // 今天结束第二次买，要么前一天买的，要么今天买的
		dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i]) // 今天结束第二次卖，要么前一天卖的，要么今天卖的
	}

	return dp[len(prices)-1][4]
}
func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end

